package com.github.kezhenxu94.playground.leetcode;

/**
 * <pre>
 * 
 * 402. Remove K Digits
 * 
 * Given a non-negative integer num represented as a string, remove k digits
 * from the number so that the new number is the smallest possible.
 * 
 * Note:
 * 
 * The length of num is less than 10002 and will be ≥ k. The given num does not
 * contain any leading zero.
 * 
 * Example 1:
 * Input: num = "1432219", k = 3
 * Output: "1219"
 * Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219
 * which is the smallest.
 * 
 * Example 2:
 * Input: num = "10200", k = 1
 * Output: "200"
 * Explanation: Remove the leading 1 and the number is 200. Note that the output
 * must not contain leading zeroes.
 * 
 * Example 3:
 * Input: num = "10", k = 2
 * Output: "0" 
 * Explanation: Remove all the digits from the number and it is left
 * with nothing which is 0.
 * 
 * </pre>
 * 
 * @author ke.zhen.xu
 *
 */
public class Solution402RemoveKDigits {

	public String removeKdigits(String num, int k) {
		if (num.length() == k)
			return "0";
		StringBuilder result = new StringBuilder(num);
		while (k-- > 0) {
			while (result.charAt(0) == '0')
				result.delete(0, 1);
			int maxIndex = 0;
			for (int i = 1; i < result.length() && result.charAt(i) >= result.charAt(i - 1); i++)
				if (result.charAt(i) > result.charAt(maxIndex))
					maxIndex = i;
			result.delete(maxIndex, maxIndex + 1);
		}
		while (result.length() > 1 && result.charAt(0) == '0')
			result.delete(0, 1);
		return result.toString();
	}
}